package com.sourcetrip.raw.adt;

import com.sourcetrip.raw.adt.abs.MyAbstractBBST;
import com.sourcetrip.raw.model.MyAVLNode;
import com.sourcetrip.raw.model.MyBinaryNode;


/**
 * @author: ZhouBert
 * @date: 2020/12/1
 * @description:
 */
public class MyAVLTree<E extends Comparable> extends MyAbstractBBST<E> {

	public MyAVLTree() {
//		guard = new MyAVLNode<>(null, null, 0);
	}

	@Override
	public void clear() {

	}


	@Override
	public boolean contains(E element) {
		return false;
	}


	/**
	 * 返回值可以用子类进行替代，但是参数不行！
	 * 进严出易！
	 *
	 * @param ele
	 * @param parent
	 * @return
	 */
	@Override
	protected MyAVLNode<E> createNode(E ele, MyBinaryNode<E> parent) {
		return new MyAVLNode<>(ele, parent, 1);
	}

	/**
	 * 此时已经完成了添加，这一步将要进行 子类转换 + 高度更新 + 旋转
	 * 1.MyBinaryNode -> MyAVLNode
	 * 2.更新 newNode 的高度
	 * 3.调整 add() ，针对最低的失衡节点进行调整就可以了，所以这是个常数次！
	 * --
	 * 把握几个规律：
	 * 1.新添加的节点肯定是叶子节点；
	 * 2.关于 平衡情况的讨论：
	 * -1-LL:g 代表 最低的失衡节点；n 代表 失衡的原因子树
	 *
	 * @param newNode parent node
	 */
	@Override
	protected void afterAdd(MyBinaryNode<E> newNode) {
		MyAVLNode<E> cur = ((MyAVLNode) newNode);
		//TODO:这里处理得还是很巧妙的！
		while ((cur = ((MyAVLNode) cur.getParent())) != null) {
			if (cur.isBalance()) {
				//平衡的时候 -> 更新高度
				//分析一下为什么能在平衡的时候更新高度：1.平衡是基于左右子树的高度更新自己的高度（左右子树的高度已经调整过）；2.如果此时平衡，那么更新自己的高度
				//既然不需要旋转，那就只要更新高度就完事了！
				cur.updateHeight();
			} else {
				//旋转调整，恢复平衡
				reBalance(cur);
				//调整完第一个不平衡的，恢复平衡，整棵树就平衡了！
				break;
			}
		}
//		guard.setLeft(root);
//		root.setParent(guard);
	}

	@Override
	protected void afterRemove(MyBinaryNode<E> deletedNode, MyBinaryNode<E> replaceNode) {
		MyAVLNode<E> cur = ((MyAVLNode) deletedNode);
		while ((cur = ((MyAVLNode) cur.getParent())) != null) {
			if (cur.isBalance()) {
				//平衡的时候 -> 更新高度
				//分析一下为什么能在平衡的时候更新高度：1.平衡是基于左右子树的高度更新自己的高度（左右子树的高度已经调整过）；2.如果此时平衡，那么更新自己的高度
				//既然不需要旋转，那就只要更新高度就完事了！
				cur.updateHeight();
			} else {
				//旋转调整，恢复平衡
				reBalance(cur);
			}
		}
	}

	/**
	 * 对失衡情况进行讨论，修正
	 * ？？如果找到类似 LL 这样的关系呢？？
	 * 有个规律：
	 * parent node = taller child of grand node;
	 * node = taller child of parent node.
	 *
	 * @param grand
	 */
	private void reBalance(MyAVLNode<E> grand) {
		MyAVLNode parent = grand.getTallerChild();
		MyAVLNode node = parent.getTallerChild();
		// LL 的情况
//		if (parent.isLeftChild() && node.isLeftChild()) {
//			//进行右旋
//			if (grand.isLeftChild()) {
//				grand.getParent().setLeft(parent);
//				grand.setLeft(parent.getRight());
//				parent.setRight(grand);
//				//更新高度
//				grand.updateHeight();
//				parent.updateHeight();
//			}
//		}
		//整理一下代码
		// L 的情况
		if (parent.isLeftChild()) {
			if (node.isLeftChild()) {
				//LL
				rotateRight(grand);
			} else {
				//LR
				rotateLeft(parent);
				rotateRight(grand);
			}

		} else {
			// R
			if (node.isLeftChild()) {
				//RL
				rotateRight(parent);
				rotateLeft(grand);
			} else {
				//RR
				rotateLeft(grand);
			}
		}
		grand.updateHeight();
		parent.updateHeight();
	}

	/**
	 * 将节点左旋
	 * 让 node.right 作为新的 root
	 * -- 优化：
	 *
	 * @param node
	 */
	private void rotateLeft(MyAVLNode node) {
		MyBinaryNode newRoot = node.getRight();
		if (node.isLeftChild()) {
			// node 作为 左子节点
			node.getParent().setLeft(newRoot);
			//1.更新 parent 节点的 parent
			newRoot.setParent(node.getParent());
		} else if (node.isRightChild()) {
			//  node 作为 右子节点
			node.getParent().setRight(newRoot);
			newRoot.setParent(node.getParent());
		} else {
			// node 作为根节点
			root = newRoot;
			newRoot.setParent(null);
		}
		node.setParent(newRoot);
		node.setRight(newRoot.getLeft());
		newRoot.setLeft(node);
		if (node.getRight() != null) {
			node.getRight().setParent(node);
		}
	}

	/**
	 * 将节点右旋
	 * 让 node.left 作为新的 root
	 *
	 * @param grand
	 */
	private void rotateRight(MyAVLNode grand) {
		MyAVLNode parent = (MyAVLNode) grand.getLeft();

		//1.确认 grand.parent 这里没有牵扯其他的线
		if (grand.isLeftChild()) {
			// node 作为 左子节点
			grand.getParent().setLeft(parent);
			//2.确认 parent.parent
			parent.setParent(grand.getParent());
		} else if (grand.isRightChild()) {
			//  node 作为 右子节点
			grand.getParent().setRight(parent);
			parent.setParent(grand.getParent());
		} else {
			root = parent;
			parent.setParent(null);
		}

		//更新 grand 的 parent
		MyBinaryNode child = parent.getRight();
		parent.setRight(grand);
		//3.确认 grand.parent
		grand.setParent(parent);
		grand.setLeft(child);
		if (child != null) {
			child.setParent(grand);
		}

		grand.updateHeight();
		parent.updateHeight();
	}

	/**
	 * 旋转代码之中有很多部分都是重复的：更新父节点，更新高度
	 * 所以这个方法作为公共部分的抽取
	 *
	 * @param grand
	 */
	private void afterRotate(MyAVLNode grand, MyAVLNode parent, MyAVLNode child) {

	}


}
